﻿#pragma once

#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>

#include <time.h>
#include <assert.h>

#include <thread>
#include <mutex>
#include <atomic>

#ifdef _WIN32
#include <windows.h>
#else
// ...
#endif

static constexpr size_t MAX_BYTES = 256 * 1024;
static constexpr size_t NFREELIST = 208;
static constexpr size_t NPAGES = 129;
static constexpr size_t PAGE_SHIFT = 13;

#ifdef _WIN64
using PAGE_ID = unsigned long long;
#elif _WIN32
using PAGE_ID = size_t;
#else
// linux
#endif

// 直接去堆上按页申请空间
inline static void *SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void *ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);

	//// 使用 VirtualQuery 查询分配的内存块信息
	//MEMORY_BASIC_INFORMATION mbi;
	//if (VirtualQuery(ptr, &mbi, sizeof(mbi)) == 0) {
	//	std::cerr << "VirtualQuery failed." << std::endl;
	//	return nullptr;
	//}

	//std::cout << "Allocated memory size: " << mbi.RegionSize << " bytes." << std::endl;  // 输出实际分配的内存大小
#else
	// linux下brk mmap等
#endif

	if (ptr == nullptr)
		throw std::bad_alloc();

	return ptr;
}

inline static void SystemFree(void *ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}

// 获取下一个对象
inline static void *&NextObj(void *obj)
{
	return *(void **)obj;
}
// 管理切分好的小对象的自由链表
class FreeList
{
public:
	// 头插
	void push(void *obj);
	// 头插多个
	void pushRange(void *start, void *end, size_t n);
	// 头删多个
	void popRange(void *&start, void *&end, size_t n);
	// 头删
	void *pop();
	// 判空
	bool empty();
	// 获取最大大小
	size_t &maxSize();
	// 获取当前大小
	size_t size();
private:
	void *m_freeList = nullptr; // 自由链表
	size_t m_maxSize = 1;		// 慢增长上限
	size_t m_size = 0;			// 当前大小
};

// 计算对象大小的对齐映射规则
class SizeClass
{
public:
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128]					8byte对齐	    freelist[0,16)
	// [128+1,1024]				16byte对齐	    freelist[16,72)
	// [1024+1,8*1024]			128byte对齐	    freelist[72,128)
	// [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
	// [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)

	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		return ((bytes + alignNum - 1) & ~(alignNum - 1));
	}

	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
	}

	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

	// 计算映射的哪一个自由链表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);

		// 每个区间有多少个链
		static int group_array[4] = {16, 56, 56, 56};
		if (bytes <= 128)
		{
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024)
		{
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024)
		{
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0];
		}
		else if (bytes <= 256 * 1024)
		{
			return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
		}
		else
		{
			assert(false);
		}

		return -1;
	}

	// 一次thread cache从中心缓存获取多少个
	static inline size_t NumMoveSize(size_t size)
	{
		assert(size > 0);

		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
		// 小对象一次批量上限高
		// 小对象一次批量上限低
		int num = MAX_BYTES / size;
		if (num < 2)
			num = 2;

		if (num > 512)
			num = 512;

		return num;
	}

	// 计算一次向系统获取几个页
	// 单个对象 8byte
	// ...
	// 单个对象 256KB
	static inline size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;

		npage >>= PAGE_SHIFT;
		if (npage == 0)
			npage = 1;

		return npage;
	}
};

// 管理多个连续页大块内存跨度结构
struct Span
{
	PAGE_ID m_pageId = 0; // 大块内存起始页的页号
	size_t m_n = 0;		  // 页的数量

	Span *m_next = nullptr; // 双向链表的结构
	Span *m_prev = nullptr;

	size_t m_objSize = 0;		// 切好的小对象的大小
	size_t m_useCount = 0;		// 切好小块内存，被分配给thread cache的计数
	void *m_freeList = nullptr; // 切好的小块内存的自由链表

	bool m_isUse = false; // 是否在被使用
};

// 带头双向循环链表
class SpanList
{
public:
	// 构造函数
	SpanList();
	// 获取头
	Span *begin();
	// 获取尾
	Span *end();
	// 判空
	bool empty();
	// 头插
	void pushFront(Span *span);
	// 头删
	Span *popFront();
	// 插入
	void insert(Span *pos, Span *newSpan);
	// 删除
	void erase(Span *pos);
	// 加锁
	void lock();
	// 解锁
	void unlock();
private:
	Span *m_head;		// 头节点，不存数据
	std::mutex m_mutex; // 桶锁
};